<?php

  require_once 'Tree.class.php';

  class HOGTree extends Tree
  {
    public $spc = null; // species name (undefined for non-leaves)
    public $len = null; // incoming edge length (distance to parrent)
    public $bs  = null; // incoming edge bootstrap value (undefined for leaves)
    public $lc  = null; // total leaves count
    public $blc = null; // bacterial leaves count
    public $d   = null; // measure of antiquity (the 'd' value defined in Req.Spec.)

    public static $bacIDs; // a list of bacterial species abbreviations

    public function __construct( Tree $source, HOGTree $parent=null )
    {
      parent::__construct( $source->label, $parent );
      $this->info = $source->info;
      foreach ( $source->children as $child )
        new HOGTree( $child, $this );
      $this->parseLabel();
      $this->defineStats();
    }

    // parses initial label into species name, bootstrap, length, etc.
    private function parseLabel()
    {
      $label = $this->label;

      // edge length
      if ( preg_match( "~:(\d+(\.\d+)?(e-\d+)?)$~", $label, $parts ) )
      {
        $this->len = floatval( $parts[1] );
        $label = preg_replace( "~:$parts[1]$~", "", $label );
      }

      // species name or bootstrap value
      if ( $this->isLeaf() )
        if ( preg_match( "~^([a-z][a-z0-9]*)(_|$)~i", $label, $parts ) )
          $this->spc = $parts[1];
        else
          echo "\nUnexpected leaf label: '$label',\n";
      else
        if ( empty($label) )
        {
          $this->bs = null;
          // if sub-root node doesn't have bootstrap value - taking root's value for it
          if ( ! $this->isRoot() )
            if ( $this->parent->isRoot() and $this->parent->bs )
              $this->bs = $this->parent->bs;
          // doing nothing for other nodes that have no bootstrap value specified
        }
        elseif ( preg_match( "~^[0-9]+$~", $label ) )
          $this->bs = intval($label);
        else
          echo "\nUnexpected non-leaf label: '$label'.\n";

      $this->label = $label;
    }

    // caches the number of all leaves and bacterial leaves
    private function defineStats( $noCache = false )
    {
      $this->lc  = $this->numberOfLeaves( $noCache );
      $this->blc = $this->numberOfBacLeaves( $noCache );
    }

    // updates the number of all leaves and bacterial leaves
    private function updateStats()
    {
      $this->defineStats( /* $noCache = */ true );
    }

    // returns the global tree root
    public function root()
    {
      if ( $this->isRoot() )
        return $this;
      else
        return $this->parent->root();
    }

    // counts all leaves
    public function numberOfLeaves( $noCache = false )
    {
      if ( !$noCache and $this->lc !== null )
        return $this->lc;
      $lc = 0;
      if ( $this->isLeaf() )
        $lc = 1;
      else
        foreach ( $this->children as $child )
          $lc += $child->numberOfLeaves( $noCache );
      return $lc;
    }

    // counts all bacterial leaves
    public function numberOfBacLeaves( $noCache = false )
    {
      if ( !$noCache and $this->blc !== null )
        return $this->blc;
      $blc = 0;
      if ( $this->isLeaf() )
        $blc = ( $this->isBacterium() ? 1 : 0 );
      else
        foreach ( $this->children as $child )
          $blc += $child->numberOfBacLeaves( $noCache );
      return $blc;
    }

    // returns a list of all non-bacterial leaves names
    public function listOfNonBacLeaves()
    {
      $nbl = array();
      if ( $this->isLeaf() and ! $this->isBacterium() )
        $nbl[] = $this->spc;
      else
        foreach ( $this->children as $child )
          $nbl = array_merge( $nbl, $child->listOfNonBacLeaves() );
      return $nbl;
    }

    // returns 'true' if it is a bacterial leaf
    public function isBacterium()
    {
      if ( !$this->isLeaf() )
        return false;
      else
        return in_array( $this->spc, self::$bacIDs );
    }

    // returns 'true' if it has some bacterial leaves
    public function hasBacLeaf()
    {
      return $this->blc > 0;
    }

    // returns 'true' if it has some non-bacterial leaves
    public function hasNonBacLeaf()
    {
      return $this->lc > $this->blc;
    }

    // recursively calculates the 'd' value (the measure of antiquity)
    public function calcD_rec()
    {
      $this->calcD();
      foreach ( $this->children as &$child )
        $child->calcD_rec();
    }

    // calculates the 'd' value for current node
    public function calcD()
    {
      if ( $this->isRoot() )
        return;
      $root = $this->root();
      $l1 = $this->lc;        // number of leaves 'below'
      $l0 = $root->lc  - $l1; // number of leaves 'above'
      $b1 = $this->blc;       // number of bacterial leaves 'below'
      $b0 = $root->blc - $b1; // number of bacterial leaves 'above'
      $d1 = $b1/$l1;          // 'percentage' of bact. leaves 'below'
      $d0 = $b0/$l0;          // 'percentage' of bact. leaves 'above'
      $d = pow( sqrt($d1) - sqrt($d0), 2 ); // 'd' as defined in Req.Spec
      $this->d = $d;
    }

    // returns the list of all 'd' values and the corresponding nodes
    // (<censored> root case in the rooted representation of unrooted tree!)
    public function getDList()
    {
      $dList = array();

      if ( $this->isRoot() and count( $this->children ) === 2 )
      { // a special case of the root with exatly two children

        // !!ASSUMPTION!! : Sequential indexing of the 'children' array
        if ( $this->children[0]->d !== $this->children[1]->d )
          exit( "Error: unequal 'd' values near root." );
        $dList[] = array( $this->children[0]->d, $this->children[0] );

        foreach ( $this->children[0]->children as $grandChild )
          $dList = array_merge( $dList, $grandChild->getDList() );
        foreach ( $this->children[1]->children as $grandChild )
          $dList = array_merge( $dList, $grandChild->getDList() );

      }
      else
      { // a regular case

        if ( ! $this->isRoot() )
          $dList[] = array( $this->d, $this );

        foreach ( $this->children as $child )
          $dList = array_merge( $dList, $child->getDList() );

      }

      return $dList;
    }

    // returns the list of all bootstrap values and the corresponding nodes
    // (the implementation is disgusting because of the undefined BS case)
    public function getBSList()
    {
      $bsList = array();

      if ( $this->isRoot() and count( $this->children ) === 2 )
      { // a special case of the root with exatly two children

        // !!ASSUMPTION!! : Sequential indexing of the 'children' array
        $c0bs = $this->children[0]->bs;
        $c1bs = $this->children[1]->bs;
        $bci = null;
        if ( $c0bs === null and $c1bs === null ) // ??UNCLEAR?? : undefined BS
          $bci = null;
        elseif ( $c0bs !== null and $c1bs === null )
          $bci = 0;
        elseif ( $c0bs === null and $c1bs !== null )
          $bci = 1;
        else
          $bci = ( $c0bs >= $c1bs ? 0 : 1 );
        if ( $bci !== null )
          $bsList[] = array( $this->children[$bci]->bs, $this->children[$bci] );

        foreach ( $this->children[0]->children as $grandChild )
          $bsList = array_merge( $bsList, $grandChild->getBSList() );
        foreach ( $this->children[1]->children as $grandChild )
          $bsList = array_merge( $bsList, $grandChild->getBSList() );

      }
      else
      { // a regular case

        if ( ! $this->isRoot() and ! $this->isLeaf() )
          $bsList[] = array( intval($this->bs), $this );
            // using 0 for undefined bootstrap values ( !!agreement!! )

        foreach ( $this->children as $child )
          $bsList = array_merge( $bsList, $child->getBSList() );

      }

      return $bsList;
    }

    // returns the parent
    public function & getParent()
    {
      return $this->parent;
    }

    // removes the parent link
    public function forgetParent()
    {
      $this->parent = null;
    }

    // unlinks the child and destroys it
    public function removeChild( HOGTree $theChild )
    {
      foreach ( $this->children as $cn => &$child )
        if ( $child === $theChild )
        {
          $this->unlinkChild( $child ); // removing the edge to the child
          $child->destroy(); // destroying the child to free memory
          break; // done
        }
    }

    // removes the edge to the given child
    public function unlinkChild( $theChild )
    {
      foreach ( $this->children as $cn => &$child )
        if ( $child === $theChild )
        {
          $child->forgetParent(); // removing the child's parent link
          unset( $this->children[$cn] ); // removing child from children array
          $this->children = array_merge( $this->children ); // re-indexing the array
          // updating the total and bacterial leaves count
          for ( $t = $this; $t !== null; $t = ( !$t->isRoot() ? $t->parent : null ) )
          {
            $t->lc  -= $child->lc;
            $t->blc -= $child->blc;
          }
          break; // done
        }
    }

    // adds the new child
    public function addChild( /*HOG*/Tree $theChild )
    {
      parent::addChild( $theChild );
      // updating the total and bacterial leaves count
      if ( $this->lc !== null )
        for ( $t = $this; $t !== null; $t = ( !$t->isRoot() ? $t->parent : null ) )
        {
          $t->lc  += $theChild->lc;
          $t->blc += $theChild->blc;
        }
    }

    // sets the global tree root to the current node
    public function becomeRoot()
    {
      if ( $this->isRoot() ) // already a root
        return; // nothing to do
      $bs = $this->bs; // temporarily storing bootstrap value of incoming edge
      $parent = $this->parent; // temporary link to ex-parent
      $parent->unlinkChild( $this ); // removing incoming edge
      $parent->becomeRoot(); // recursively making ex-parent a root
      $this->addChild( $parent ); // making ex-parent a new child
      $parent->bs = $bs; // passing bootstrap value to the lower end of the edge
    }

    // recursively removes all non-bacterial subtrees
    public function removeNonBacBranches()
    {
      foreach ( $this->children as &$child )
        if ( !$child->hasBacLeaf() )
          $this->removeChild( $child );
        else
          $child->removeNonBacBranches();
    }

    // removes the incoming edge end returns the two parts of the splitted tree
    public function separate()
    {

      if ( $this->isRoot() )
        return false;

      $root = $this->root();
      $parent = $this->parent;

      if ( $parent->isRoot() and count( $parent->children ) === 2 )
      { // a special case of the root with exatly two children

        // !!ASSUMPTION!! : Sequential indexing of the 'children' array
        $child0 = $parent->children[0];
        $child1 = $parent->children[1];
        $parent->unlinkChild( $child0 );
        $parent->unlinkChild( $child1 );
        return array( $child0, $child1 );

      }
      else
      { // a regular case

        $parent->unlinkChild( $this );
        return array( $root, $this );

      }

    }

    // recursively removes all 'transt nodes' = nodes having the only child
    public function removeTransitNodes()
    {

      // recursively call the method for all the children 
      foreach ( $this->children as &$child )
        $child->removeTransitNodes();

      // replacing every "transit" child with it's only child
      foreach ( $this->children as $n => &$child )
        if ( $child->childrenCount() == 1 ) // $child is a "transit" node
        {
          $bs = $child->bs;
          $child = array_pop($child->children); // replacing it with it's only child
          $child->setParent($this); // correcting new child's parrent link
          // it's important to "pop" the "only child" from the old child's children,
          // otherwice it will be automatically destroyed when the old child dies
          if ( $bs > $child->bs )
            $child->bs = $bs;
        }

      // checking if the root is "transit" (has only one child)
      if ( $this->isRoot() and $this->childrenCount() == 1 )
      {
        $child = array_pop($this->children);
        $child->forgetParent();
        return $child;
      }

      return $this;

    }

    public function toNewickCompact( $root=true )
    {
      $result = "";

      if ( count($this->children) )
      {
        $result .= "(";
        $first_child = true;
        foreach ( $this->children as &$child )
        {
          if ( !$first_child )
            $result .= ",";
          $result .= $child->toNewickCompact(false);
          $first_child = false;
        }
        $result .= ")";
      }
      if ( !$this->isRoot() )
        if ( $this->isLeaf() )
          $result .= $this->label;
        else
          $result .= $this->bs;
      if ( $root )
        $result .= ";";

      return $result;
    }

  }

  HOGTree::$bacIDs = null;

?>
